/* Copyright (c) 2025 LiuYing
*    Key Laboratory of Cyberspace Security Defense,Institute of Information Engineering, CAS
*    School of Cyber Security, University of Chinese Academy of Sciences     
*
* This file is part of the openHiTLS project.
*
* openHiTLS is licensed under the Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*
*     http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
* See the Mulan PSL v2 for more details.
*/
#include<stdint.h>
#include "polarlac_param.h"
#if defined LAC256
// twiddle factors for 1024 length in naive NTT
static int16_t fn_1024[DIM_N]={
1,6531,18275,350,17782,6342,10693,11779,3828,5520,3465,12624,14860,915,11544,2894,7333,2889,2665,4363,364,17860,16220,16802,15698,17725,8171,1266,10917,83,7816,5319,11421,10633,1916,15822,11861,8725,6128,3925,14945,3060,16547,14211,3429,17137,11208,2005,9074,199,4082,5424,9819,17915,15403,8112,7500,6019,13145,7514,2245,7860,13950,11564,5329,2195,5936,3417,14658,8829,6594,5926,12514,15445,13552,11279,772,9723,7055,12138,18030,3926,8375,6414,4291,6361,4043,8777,5688,5833,4513,36,2145,18348,11317,13430,15176,215,16915,2896,512,7499,11269,13303,11345,11968,13924,7655,6038,5991,4512,11938,5587,9790,2038,1552,12597,4528,438,3463,4756,1831,4305,5630,588,6164,17694,3037,18360,2495,11534,11316,10657,16292,12030,6484,15484,2566,5117,98,2767,6937,5206,9934,17681,10299,8218,13295,10294,4963,14085,8465,15325,14818,11806,18180,14111,12374,855,17239,14185,16410,7596,6273,498,8230,13481,8403,14995,16249,8647,13278,7745,2443,11301,1099,1186,3906,15375,9574,2100,948,18427,16113,5490,3005,17364,4468,2012,16076,13898,3746,16509,5662,9064,8621,17513,638,16329,9794,8128,15361,6086,6118,17376,9108,1109,17143,10986,8330,15347,11036,118,14905,18222,4434,8735,16583,2345,15805,9312,6205,3344,14992,16565,2738,216,9788,17923,5563,6848,5830,1300,11120,15796,12608,1618,5049,2418,13310,16108,4217,17123,15735,2069,1250,4892,5263,3039,13801,17529,12969,12375,10853,17081,17928,7673,11469,4244,12765,220,17479,2106,3268,8475,14359,6559,16970,12675,16255,6547,12330,8593,10831,6348,2971,9589,8858,14877,1344,9532,5251,5450,18260,6589,10137,9619,2025,2851,2551,10367,2468,5732,16702,15994,15436,1292,14171,17060,9808,6826,9612,9039,11243,3361,15421,3519,15071,5516,6914,13256,13568,18107,9122,14642,14931,9463,15437,16352,12543,5023,12906,17418,6915,11101,3642,15610,14420,2425,3728,3943,832,6563,6228,13727,11358,4525,4676,3937,16945,3505,15802,17633,10172,13113,1285,11075,18166,16349,11383,15911,7920,4187,9158,2042,9243,2347,10434,16267,10398,9559,15691,1184,9277,7445,15474,3402,6697,12326,4195,6390,778,12562,15572,5968,9646,13881,3317,329,10471,14072,15727,7017,3589,11294,10681,3549,8238,2373,14343,12159,1065,8047,2474,451,14634,14808,11530,1327,3127,17866,1956,15854,4313,457,16954,1526,12486,4618,3770,7676,12629,16694,15752,16700,18072,13073,16540,17395,4166,5523,15765,12150,16018,16282,16198,8064,2903,17826,17211,3741,8746,12709,17113,1175,5797,2858,11402,9261,4918,5365,16115,248,16017,9655,15945,4449,6011,1981,16378,363,11329,679,10629,3316,16454,7305,4351,7089,12996,159,6181,11744,351,1469,8879,7527,16459,2197,7733,3101,13197,1267,16793,2577,1058,4668,16959,18209,11696,7710,13487,16831,7282,12999,12504,10654,15132,2647,15836,5733,4800,9505,13244,9716,8810,3419,7126,12788,16938,4624,6090,6728,14729,502,15921,12849,9803,4992,13208,3883,14498,17660,2179,11536,5945,5532,812,10728,735,8669,9496,12773,11138,15412,11592,16493,11764,8955,15629,4451,640,13556,537,14813,7319,12793,12727,6336,16764,3473,9573,4256,17405,974,1809,12005,9106,11081,2053,337,7420,5006,12477,1671,965,3735,6426,18159,16940,8771,12070,15090,9972,4309,13321,1199,15077,8895,10862,13931,16506,15750,7110,18388,1033,9675,17534,1289,13011,5661,13826,8779,9019,4003,5599,12681,142,11533,4785,2653,18156,16591,6647,14541,455,997,4558,8371,17156,8663,7176,13721,9038,885,10406,7634,14822,10773,18135,12135,10218,9750,9668,7872,2395,4423,2102,1620,18111,14608,14073,14494,6859,13004,8293,9864,16882,13576,2126,11653,14319,10212,3978,8608,16631,6301,9375,18257,11823,1130,6830,5790,8407,1690,14456,9475,1644,12318,7246,7654,16411,17770,1702,12589,7579,9873,1929,6871,8579,5794,16098,6198,270,6194,11012,16730,11239,4533,1625,2673,1312,2630,15407,8419,17283,2139,16028,12265,11330,3222,10829,7048,3287,3840,10160,1569,16824,4872,3674,4410,9364,17237,4516,4638,5359,14253,18126,15285,11640,11529,15527,3285,16756,12612,10328,16501,8713,10706,4517,4288,5201,2709,15232,14370,8067,6009,922,9094,1788,5435,12460,7621,3651,951,17493,15639,1056,12756,10709,12182,3814,9127,14548,14141,5541,6190,3321,17362,9839,7137,13123,15200,9495,8915,12451,10771,5073,2730,4919,11052,15417,9224,2900,17248,2625,4334,10699,15682,5394,10277,4534,16771,2515,852,16079,12848,3272,4197,736,462,12743,14270,122,12599,17590,10973,15592,17401,6486,8581,6191,8244,17204,11924,14652,14607,7542,16202,9842,2271,11769,4964,14670,8307,4698,12644,16557,11445,1480,8137,408,4664,9268,11517,10887,5181,12556,15099,13452,10648,12812,13773,16856,17393,9537,1000,5718,7897,18206,12588,1048,1860,313,12369,8533,18029,15828,3002,11783,4942,19,6584,14348,10409,275,8705,4983,7085,5305,5641,12237,11939,2019,14309,15202,6437,12807,4445,16753,16577,7378,286,6133,10111,7935,1801,2077,10370,3628,7261,11915,14041,16029,7657,17571,6772,7165,10636,8172,15348,17567,2526,18204,6418,17749,14544,1615,6173,2892,1863,1473,574,6895,3765,18026,13419,9007,16426,16579,3745,16437,16247,8809,13594,9086,6980,1571,3140,9844,8971,9527,1923,6240,10023,4630,1604,5780,309,8882,6477,15985,14332,17951,2803,2424,15399,421,114,7214,6288,16637,1878,7273,17071,7917,12433,2558,14288,7082,9755,5457,7177,16301,8880,5062,3753,13386,15315,4807,8386,4523,2188,4253,732,6545,13375,16571,2726,15661,11684,14017,280,3813,11059,5835,2050,6192,7894,17046,17059,3277,14329,16791,9690,4901,17352,18261,12166,9916,13237,77,6124,14667,9357,5172,7309,12042,6457,14396,15988,13116,17650,10601,15991,14276,17176,11651,4504,14989,7255,9595,12462,7627,3335,11512,16191,11733,4009,7919,18365,16717,10744,13066,7402,11136,10196,10080,11465,3069,13397,12789,1650,11278,15795,6077,17480,6311,3110,16677,12114,2098,3020,310};
static int16_t f_1024[DIM_N]={
1,11902,18083,158,6654,7740,12091,651,15539,6889,17518,3573,5809,14968,12913,14605,13114,10617,18350,7516,17167,10262,708,2735,1631,2213,573,18069,14070,15768,15544,11100,6869,4483,10573,16188,10919,5288,12414,10933,10321,3030,518,8614,13009,14351,18234,9359,16428,7225,1296,15004,4222,1886,15373,3488,14508,12305,9708,6572,2611,16517,7800,7012,15396,739,12269,17845,12803,14128,16602,13677,14970,17995,13905,5836,16881,16395,8643,12846,6495,13921,12442,12395,10778,4509,6465,7088,5130,7164,10934,17921,15537,1518,18218,3257,5003,7116,85,16288,18397,13920,12600,12745,9656,14390,12072,14142,12019,10058,14507,403,6295,11378,8710,17661,7154,4881,2988,5919,12507,11839,9604,3775,15016,12497,16238,13104,505,1352,7580,6058,5464,904,4632,15394,13170,13541,17183,16364,2698,1310,14216,2325,5123,16015,13384,16815,5825,2637,7313,17133,12603,11585,12870,510,8645,18217,15695,1868,3441,15089,12228,9121,2628,16088,1850,9698,13999,211,3528,18315,7397,3086,10103,7447,1290,17324,9325,1057,12315,12347,3072,10305,8639,2104,17795,920,9812,9369,12771,1924,14687,4535,2357,16421,13965,1069,15428,12943,2320,6,17485,16333,8859,3058,14527,17247,17334,7132,15990,10688,5155,9786,2184,3438,10030,4952,10203,17935,12160,10837,2023,4248,1194,17578,6059,4322,253,6627,3615,3108,9968,4348,13470,8139,5138,10215,8134,752,8499,13227,11496,15666,18335,13316,15867,2949,11949,6403,2141,7776,7117,6899,15938,73,3935,14550,5225,13441,8630,5584,2512,17931,3704,11705,12343,13809,1495,5645,11307,15014,9623,8717,5189,8928,13633,12700,2597,15786,3301,7779,5929,5434,11151,1602,4946,10723,6737,224,1474,13765,17375,15856,1640,17166,5236,15332,10700,16236,1974,10906,9554,16964,18082,6689,12252,18274,5437,11344,14082,11128,1979,15117,7804,17754,7104,18070,2055,16452,12422,13984,2488,8778,2416,18185,2318,13068,13515,9172,7031,15575,12636,17258,1320,5724,9687,14692,1222,607,15530,10369,2235,2151,2415,6283,2668,12910,14267,1038,1893,5360,361,1733,2681,1739,5804,10757,14663,13815,5947,16907,1479,17976,14120,2579,16477,567,15306,17106,6903,3625,3799,17982,15959,10386,17368,6274,4090,16060,10195,14884,7752,7139,14844,11416,2706,4361,7962,18104,15116,4552,8787,12465,2861,5871,17655,12043,14238,6107,11736,15031,2959,10988,9156,17249,2742,8874,8035,2166,7999,16086,9190,16391,9275,14246,10513,2522,7050,2084,267,7358,17148,5320,8261,800,2631,14928,1488,14496,13757,13908,7075,4706,12205,11870,17601,14490,14705,16008,4013,2823,14791,7332,11518,1015,5527,13410,5890,2081,2996,8970,3502,3791,9311,326,4865,5177,11519,12917,3362,14914,3012,15072,7190,9394,8821,11607,8625,1373,4262,17141,2997,2439,1731,12701,15965,8066,15882,15582,16408,8814,8296,11844,173,12983,13182,8901,17089,3556,9575,8844,15462,12085,7602,9840,6103,11886,2178,5758,1463,11874,4074,9958,15165,16327,954,18213,5668,14189,6964,10760,18123,15413,16335,6319,1756,15323,12122,953,12356,2638,7155,16783,5644,5036,15364,6968,8353,8237,7297,11031,5367,7689,1716,68,10514,14424,6700,2242,6921,15098,10806,5971,8838,11178,3444,13929,6782,1257,4157,2442,7832,783,5317,2445,4037,11976,6391,11124,13261,9076,3766,12309,18356,5196,8517,6267,172,1081,13532,8743,1642,4104,15156,1374,1387,10539,12241,16383,12598,7374,14620,18153,4416,6749,2772,15707,1862,5058,11888,17701,14180,16245,13910,10047,13626,3118,5047,14680,13371,9553,2132,11256,12976,8678,11351,4145,15875,6000,10516,1362,11160,16555,1796,12145,11219,18319,18012,3034,16009,15630,482,4101,2448,11956,9551,18124,12653,16829,13803,8410,12193,16510,8906,9462,8589,15293,16862,11453,9347,4839,9624,2186,1996,14688,1854,2007,9426,5014,407,14668,11538,17859,16960,16570,15541,12260,16818,3889,684,12015,229,15907,866,3085,10261,7797,11268,11661,862,10776,2404,4392,6518,11172,14805,8063,16356,16632,10498,8322,12300,18147,11055,1856,1680,13988,5626,11996,3231,4124,16414,6494,6196,12792,13128,11348,13450,9728,18158,8024,4085,11849,18414,13491,6650,15431,2605,404,9900,6064,18120,16573,17385,5845,227,10536,12715,17433,8896,1040,1577,4660,5621,7785,4981,3334,5877,13252,7546,6916,9165,13769,18025,10296,16953,6988,1876,5789,13735,10126,3763,13469,6664,16162,8591,2231,10891,3826,3781,6509,1229,10189,12242,9852,11947,1032,2841,7460,843,5834,18311,4163,5690,17971,17697,14236,15161,5585,2354,17581,15918,1662,13899,8156,13039,2751,7734,14099,15808,1185,15533,9209,3016,7381,13514,15703,13360,7662,5982,9518,8938,3233,5310,11296,8594,1071,15112,12243,12892,4292,3885,9306,14619,6251,7724,5677,17377,2794,940,17482,14782,10812,5973,12998,16645,9339,17511,12424,10366,4063,3201,15724,13232,14145,13916,7727,9720,1932,8105,5821,1677,15148,2906,6904,6793,3148,307,4180,13074,13795,13917,1196,9069,14023,14759,13561,1609,16864,8273,14593,15146,11385,7604,15211,7103,6168,2405,16294,1150,10014,3026,15803,17121,15760,16808,13900,7194,1703,7421,12239,18163,12235,2335,12639,9854,11562,16504,8560,10854,5844,16731,663,2022,10779,11187,6115,16789,8958,3977,16743,10026,12643,11603,17303,6610,176,9058,12132,1802,9825,14455,8221,4114,6780,16307,4857,1551,8569,10140,5429,11574,3939,4360,3825,322,16813,16331,14010,16038,10561,8765,8683,8215,6298,298,7660,3611,10799,8027,17548,9395,4712,11257,9770,1277,10062,13875,17436,17978,3892,11786,1842,277,15780,13648,6900,18291,5752,12834,14430,9414,9654,4607,12772,5422,17144,899,8758,17400,45,11323,2683,1927,4502,7571,9538,3356,17234,5112,14124,8461,3343,6363,9662,1493,274,12007,14698,17468,16762,5956,13427,11013,18096,16380,7352,9327,6428,16624,17459,1028,14177,8860,14960,1669,12097,5706,5640,11114,3620,17896,4877,17793,13982,2804,9478,6669,1940,6841,3021,7295,5660,8937,9764,17698,7705,17621,12901,12488,6897,16254,773};

// twiddle factors for 1024 length in NTT use Montgomery
const int M_1024[DIM_N]={10237,1356,4658,6948,8459,2028,9087,11370,17111,11095,6113,16558,12704,2891,1965,4047,8745,8161,765,872,2802,14326,18109,3751,1532,14806,16006,1643,16483,1753,13172,17954,14691,3156,1380,17476,2886,9940,4837,14718,16498,7553,10802,4771,6241,4608,9304,9256,6651,9533,18256,5292,1954,5938,4629,1879,4055,13417,4465,18342,14547,2775,5699,3942,9726,388,11664,12428,9326,5474,1132,1459,14901,10624,5066,17244,13640,14584,1541,18286,3481,6522,2992,1772,1128,12201,6106,7707,16642,7934,6483,18305,4662,14639,724,9596,3388,7428,17686,6088,6372,12251,7039,18240,10865,10698,16032,5552,5157,3276,14679,16949,14953,9,15283,17011,16654,12574,4587,4072,5619,16019,15415,12752,10198,4709,10820,11731,8452,11610,10193,8920,9215,17853,237,17908,4341,1117,14576,7844,12691,10153,4019,17930,6770,12536,17887,10076,16650,4883,5219,2672,17195,6709,11274,9092,13319,1062,15393,16534,15104,9241,9858,14562,10518,11700,15559,13133,12224,1621,4073,1944,5232,13843,2829,6333,12168,4545,12921,777,4822,8918,12310,10297,17346,15941,5849,6643,7183,188,7932,7162,8889,8542,14879,14406,1223,5924,9529,4091,18207,17067,17275,13065,18095,4482,16538,10731,3949,3152,2780,18108,9821,12544,15087,8812,1712,10674,5999,9344,9901,467,2447,18379,10738,10746,17665,16401,14102,8894,2277,14089,17907,11665,9376,230,10632,481,15980,16167,14411,17776,8754,11641,836,3748,15376,16105,13772,10325,17551,9187,11299,6470,2759,9988,5488,8376,17680,3768,3314,3392,10945,17054,12877,8341,11497,9298,4088,7744,17684,11459,4265,2452,8151,18110,6868,7419,2403,7510,13215,3859,13392,17000,5246,13112,617,11233,6248,13459,8198,11706,6245,12299,8672,10656,9743,817,8978,18378,16692,2690,17016,17372,10579,4565,5921,16050,7013,14331,16359,2961,17544,336,11431,2211,7316,2460,5351,16846,10814,9411,5657,6135,1492,11628,3893,6076,13907,7226,14654,1138,15579,14722,8540,14915,296,16144,8531,11435,10067,15499,13085,2747,8675,11816,11825,13238,11506,12778,6919,8706,5594,208,932,4002,8040,12056,1557,12184,13119,3605,10127,1833,12443,12569,6337,4862,7377,13758,14146,1330,8586,1980,7454,521,18233,2543,13167,3732,1169,3477,18061,3624,4902,15274,18103,1431,16140,10446,12067,8502,62,17829,8637,3267,14937,6111,17811,11411,2016,5334,13266,5146,14760,11403,8911,4760,12254,13221,17766,12444,4135,1340,10258,9476,4721,12875,9835,11813,4940,5390,12099,14731,7648,14091,8194,4015,16495,6393,11276,3721,1919,16982,10159,8062,4175,4518,3938,5043,9598,12338,13455,4494,489,4750,14903,5253,3197,13451,10998,12970,1682,17507,10739,17277,17037,7059,17805,9091,5579,12841,3302,17185,15258,1200,3959,13163,2429,11419,3311,2232,11880,3783,3126,10575,7980,7289,11037,9617,15597,3249,5696,2782,2936,4696,15370,13785,829,13330,16482,13655,13311,4113,16657,13734,14469,9481,18023,13508,18377,2924,8848,17266,14600,17124,15758,4059,6828,4241,8723,11943,12989,2493,12234,11632,4908,17594,17155,3531,8091,13343,11932,11601,4597,14083,10994,5279,5026,14066,16944,7965,9148,4235,10823,12891,13909,1855,14338,1838,14277,8973,11493,1607,17018,12001,2374,2441,17948,2941,2898,14580,2682,4792,203,17050,5153,14018,15311,15549,1584,4191,7790,1410,1064,18176,16218,3740,17528,6438,13959,15044,17732,11586,160,12712,2466,13437,15898,15182,16738,8188,9748,15039,2152,8766,10211,15880,18389,7564,6952,3033,405,9136,9742,12719,12840,6323,17343,14781,1968,5207,2417,6779,9142,1915,11771,10791,16995,9252,6008,12824,14488,4539,15021,1725,6803,6863,12673,3193,13600,11406,7861,4286,17255,11476,1794,11659,11125,12922,11818,4387,6701,4289,10356,4359,6270,9677,4722,973,10319,2341,10135,17215,10376,5948,1129,299,17646,2910,13748,1045,14646,4189,8490,1726,1762,5430,16532,8411,14217,4206,2540,17473,16891,12049,4007,13290,8460,8559,8929,11720,11130,8711,11028,6137,16972,6503,9642,4774,6977,411,3614,8794,10924,8934,6710,7769,13399,7418,2753,7668,14493,328,14231,3475,10766,9284,13241,7768,14307,2140,6753,12107,4312,14481,725,16127,13137,10565,7283,8133,8801,5237,10350,2039,3212,818,8628,18220,7301,15093,7721,11596,2763,17679,5838,8534,3800,6982,7889,2824,14655,7669,7068,4876,12809,6625,3808,3931,11490,447,9447,3106,1072,15125,14954,6540,2582,15280,16003,483,12262,10170,16502,15244,17360,15210,3637,11543,8518,264,18198,13587,3115,12466,5521,2703,15799,13768,10646,18183,465,13903,262,15286,18332,3957,15958,1516,10452,4613,7554,8466,2662,3203,3363,10050,18173,16209,4214,1165,15120,3139,7330,1729,102,2574,2317,17267,18175,10838,3898,1865,2061,4301,6156,2463,7758,13614,9247,5649,184,3559,7794,9101,6685,10391,12884,17192,16686,370,17964,15272,5176,16767,11677,5166,3663,15452,11102,10173,9360,6332,14193,13359,7963,6860,13723,3667,14761,17934,8753,5110,12615,11488,16027,9763,10821,18262,4551,8585,15368,723,5012,14797,3837,9000,2043,15774,9001,2694,15616,16740,7593,5113,16884,3198,15434,7810,13017,1031,15596,15151,5854,2432,3587,16787,4677,2006,11809,907,14344,4158,17335,17832,7587,2793,7136,6592,15358,9145,18013,3497,11061,464,7952,8751,15461,18250,2921,17329,17740,8535,7373,6067,14778,18363,11190,13478,1548,8704,8437,5810,12563,3670,547,14888,5739,7120,2220,10482,17900,2814,10987,14861,15189,11386,401,1445,10374,11319,15444,17821,11437,4531,5089,1560,6990,11582,5001,16688,2461,17648,9686,15643,17984,16861,16933,9856,15804,9557,9245,11020,13930,9975,9096,14850,606,13124,17174,17022,14592,1742,8557,15344,12036,8804,9994,17994,6186,14063,755,9294,9741,6188,2686,12483,18004,17,2549,2520,2784,7366,14827,6588,16758,9777,6515,6101,2878,12991,17134,13844,2479,6175,16164,1293,8275,16902,4338,18390,15050,6794,14644,9560,8806,1026,4294,7521,3569,9827,6422,7007,17572,17307,13629,16475,3279,14436,12227,2781,3599,2994};  //包含预计算用于Montgomery的正幂次本原根
const int Mn_1024[DIM_N]={10237,17077,11485,13775,7063,9346,16405,9974,14386,16468,15542,5729,1875,12320,7338,1322,479,5261,16680,1950,16790,2427,3627,16901,14682,324,4107,15631,17561,17668,10272,9688,14491,12734,15658,3886,91,13968,5016,14378,16554,13804,12495,16479,13141,177,8900,11782,9177,9129,13825,12192,13662,7631,10880,1935,3715,13596,8493,15547,957,17053,15277,3742,6702,7613,13724,8235,5681,3018,2414,12814,14361,13846,5859,1779,1422,3150,18424,3480,1484,3754,15157,13276,12881,2401,7735,7568,193,11394,6182,12061,12345,747,11005,15045,8837,17709,3794,13771,128,11950,10499,1791,10726,12327,6232,17305,16661,15441,11911,14952,147,16892,3849,4793,1189,13367,7809,3532,16974,17301,12959,9107,6005,6769,18045,8707,8445,15674,11963,7134,9246,882,8108,4661,2328,3057,14685,17597,6792,9679,657,4022,2266,2453,17952,7801,18203,9057,6768,526,4344,16156,9539,4331,2032,768,7687,7695,54,15986,17966,8532,9089,12434,7759,16721,9621,3346,5889,8612,325,15653,15281,14484,7702,1895,13951,338,5368,1158,1366,226,14342,8904,12509,17210,4027,3554,9891,9544,11271,10501,18245,11250,11790,12584,2492,1087,8136,6123,9515,13611,17656,5512,13888,6265,12100,15604,4590,13201,16489,14360,16812,6209,5300,2874,6733,7915,3871,8575,9192,3329,1899,3040,17371,5114,9341,7159,11724,1238,15761,13214,13550,1783,8357,546,5897,11663,503,14414,8280,5742,10589,3857,17316,14092,525,18196,580,9218,9513,8240,6823,9981,6490,9710,14192,11605,14374,2675,1309,3833,1167,9585,15509,56,4925,410,8952,3964,4699,1776,14320,5122,4778,1951,5103,17604,4648,3063,13737,15497,15651,12737,15184,2836,8816,7396,11144,10453,7858,15307,14650,6553,16201,15122,7014,16004,5270,14474,17233,3175,1248,15131,5592,12854,9342,628,11374,1396,1156,7694,926,16751,5463,7435,4982,15236,13180,3530,13683,17944,13939,4978,6095,8835,13390,14495,13915,14258,10371,8274,1451,16514,14712,7157,12040,1938,14418,10239,4342,10785,3702,6334,13043,13493,6620,8598,5558,13712,8957,8175,17093,14298,5989,667,5212,6179,13673,9522,7030,3673,13287,5167,13099,16417,7022,622,12322,3496,15166,9796,604,18371,9931,6366,7987,2293,17002,330,3159,13531,14809,372,14956,17264,14701,5266,15890,200,17912,10979,16453,9847,17103,4287,4675,11056,13571,12096,5864,5990,16600,8306,14828,5314,6249,16876,6377,10393,14431,17501,18225,12839,9727,11514,5655,6927,5195,6608,6617,9758,15686,5348,2934,8366,6998,9902,2289,18137,3518,9893,3711,2854,17295,3779,11207,4526,12357,14540,6805,16941,12298,12776,9022,7619,1587,13082,15973,11117,16222,7002,18097,889,15472,2074,4102,11420,2383,12512,13868,7854,1061,1417,15743,1741,55,9455,17616,8690,7777,9761,6134,12188,6727,10235,4974,12185,7200,17816,5321,13187,1433,5041,14574,5218,10923,16030,11014,11565,323,10282,15981,14168,6974,749,10689,14345,9135,6936,10092,5556,1379,7488,15041,15119,14665,753,10057,12945,15439,14834,15652,6206,3997,15154,1958,4804,1126,861,11426,12011,8606,14864,10912,14139,17407,9627,8873,3789,11639,3383,43,14095,1531,10158,17140,2269,12258,15954,4589,1299,5442,15555,12332,11918,8656,1675,11845,3606,11067,15649,15913,15884,18416,429,5950,15747,12245,8692,9139,17678,4370,12247,439,8439,9629,6397,3089,9876,16691,3841,1411,1259,5309,17827,3583,9337,8458,4503,7413,9188,8876,2629,8577,1500,1572,449,2790,8747,785,15972,1745,13432,6851,11443,16873,13344,13902,6996,612,2989,7114,8059,16988,18032,7047,3244,3572,7446,15619,533,7951,16213,11313,12694,3545,17886,14763,5870,12623,9996,9729,16885,4955,7243,70,3655,12366,11060,9898,693,1104,15512,183,2972,9682,10481,17969,7372,14936,420,9288,3075,11841,11297,15640,10846,601,1098,14275,4089,17526,6624,16427,13756,1646,14846,16001,12579,3282,2837,17402,5416,10623,2999,15235,1549,13320,10840,1693,2817,15739,9432,2659,16390,9433,14596,3636,13421,17710,3065,9848,13882,171,7612,8670,2406,6945,5818,13323,9680,499,3672,14766,4710,11573,10470,5074,4240,12101,9073,8260,7331,2981,14770,13267,6756,1666,13257,3161,469,18063,1747,1241,5549,8042,11748,9332,10639,14874,18249,12784,9186,4819,10675,15970,12277,14132,16372,16568,14535,7595,258,1166,16116,15859,18331,16704,11103,15294,3313,17268,14219,2224,260,8383,15070,15230,15771,9967,10879,13820,7981,16917,2475,14476,101,3147,18171,4530,17968,250,7787,4665,2634,15730,12912,5967,15318,4846,235,18169,9915,6890,14796,3223,1073,3189,1931,8263,6171,17950,2430,3153,15851,11893,3479,3308,17361,15327,8986,17986,6943,14502,14625,11808,5624,13557,11365,10764,3778,15609,10544,11451,14633,9899,12595,754,15670,6837,10712,3340,11132,213,9805,17615,15221,16394,8083,13196,9632,10300,11150,7868,5296,2306,17708,3952,14121,6326,11680,16293,4126,10665,5192,9149,7667,14958,4202,18105,3940,10765,15680,11015,5034,10664,11723,9499,7509,9639,14819,18022,11456,13659,8791,11930,1461,12296,7405,9722,7303,6713,9504,9874,9973,5143,14426,6384,1542,960,15893,14227,4216,10022,1901,13003,16671,16707,9943,14244,3787,17388,4685,15523,787,18134,17304,12485,8057,1218,8298,16092,8114,17460,13711,8756,12163,14074,8077,14144,11732,14046,6615,5511,7308,6774,16639,6957,1178,14147,10572,7027,4833,15240,5760,11570,11630,16708,3412,13894,3945,5609,12425,9181,1438,7642,6662,16518,9291,11654,16016,13226,16465,3652,1090,12110,5593,5714,8691,9297,18028,15400,11481,10869,44,2553,8222,9667,16281,3394,8685,10245,1695,3251,2535,4996,15967,5721,18273,6847,701,3389,4474,11995,905,14693,2215,257,17369,17023,10643,14242,16849,2884,3122,4415,13280,1383,18230,13641,15751,3853,15535,15492,485,15992,16059,6432,1415,16826,6940,9460,4156,16595,4095,16578,4524,5542,7610,14198,9285,10468,1489,4367,13407,13154,7439,4350,13836,6832,6501,5090,10342,14902,1278,839,13525,6801,6199,15940,5444};


#endif